package text111;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution12 {
	  public List<List<Integer>> levelOrder(TreeNode root) {
	     	//创建队列
		Queue<TreeNode> queue = new LinkedList();
		//创建动态数组
		List<List<Integer>> res = new ArrayList<List<Integer>>();
//		ArrayList<Integer> res = new ArrayList<Integer>();
//		List<Integer>list = new ArrayList<Integer>();
		//要判断根节点是否为空值		
		//根左右依次入队
		if (root==null) {
			return res;
		}
		if (root!=null) {
			queue.add(root);
	     //记录奇偶数反转数组
			int f = 0;
			while(!queue.isEmpty()) {
				//备份
				//TreeNode tmpNode = queue.poll();
	   //记录每一行的数
		    List<Integer>list = new ArrayList<Integer>();
				int size = queue.size();
				for (int i = 0; i <size; i++) {
	             TreeNode tmpNode = queue.poll();
						list.add(tmpNode.val);
						if (tmpNode.left!=null) {queue.add(tmpNode.left);}
						if (tmpNode.right!=null) {queue.add(tmpNode.right);	}	
				}		
				f++;
				//判断奇偶数
				if ((f%2)==0) {
					Collections.reverse(list);
				}
				res.add(list);
				//queue.size();
				//res.add(tmpNode.val);
			}
	     	System.out.println(f);
		}
		
		return res;
	    }
}

/*
	 public List<List<Integer>> levelOrder(TreeNode root) {
            	//创建队列
		Queue<TreeNode> queue = new LinkedList();
		//创建动态数组
		List<List<Integer>> res = new ArrayList<List<Integer>>();
	//	ArrayList<Integer> res = new ArrayList<Integer>();
	//	List<Integer>list = new ArrayList<Integer>();
		//要判断根节点是否为空值		
		//根左右依次入队
		if (root==null) {
			return res;
		}
		if (root!=null) {
			queue.add(root);
            //记录反转
			int f = 0;
			while(!queue.isEmpty()) {
				//备份
				//TreeNode tmpNode = queue.poll();
          //记录每一行的数
		    List<Integer>list = new ArrayList<Integer>();
				int size = queue.size();

				if ((f%2)==0) {
					for (int i = 0; i <size; i++) {
					TreeNode tmpNode = queue.poll();
					list.add(tmpNode.val);
					if (tmpNode.right!=null) {queue.add(tmpNode.right);	}	
					if (tmpNode.left!=null) {queue.add(tmpNode.left);}
					}
				}
               	if ((f%2)==1) {
					for (int i = 0; i <size; i++) {
                    TreeNode tmpNode = queue.poll();
						list.add(tmpNode.val);
						if (tmpNode.left!=null) {queue.add(tmpNode.left);}
						if (tmpNode.right!=null) {queue.add(tmpNode.right);	}	
				}
				}
				
				f++;
                
              res.add(list);
				//queue.size();
				//res.add(tmpNode.val);
			}
            	System.out.println(f);
		}
    	
		return res;
    }

*/